package afi;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class HashingProblems {

	/**
	 * Problem 1.8 in AFI: Given a dictionary of English words, return the set
	 * of all words grouped together into subsets of words that are anagrams of
	 * each other
	 * 
	 * @param dictionary dictionary of words
	 * @return a list of anagram groups
	 */
	public static List<List<String>> findAnagramGroups(List<String> dictionary) {

		HashMap<String, List<String>> anagramMap = new HashMap<String, List<String>>();

		for (String word : dictionary) {
			char[] wordArray = word.toLowerCase().toCharArray();
			Arrays.sort(wordArray);
			String wordKey = new String(wordArray);

			List<String> anagramList = anagramMap.get(wordKey);
			if (anagramList == null) {
				anagramList = new LinkedList<String>();
				anagramMap.put(wordKey, anagramList);
			}
			anagramList.add(word);
		}

		List<List<String>> anagramGroups = new LinkedList<List<String>>();
		for (List<String> anagramList : anagramMap.values()) {
			if (anagramList.size() > 1)
				anagramGroups.add(anagramList);
		}

		return anagramGroups;
	}
	
	
	/**
	 * Problem 1.9 in AFI: Given a sorted integer array A and a target integer S, 
	 * determine if there exist a pair of indices (not necessarily distinct) such 
	 * that A[i] + A[j] = S
	 * @param a sorted integer array
	 * @param sum target integer
	 * @return true if if there exist a pair of indices in A that sum to S
	 */
	public static boolean pairSumExists(int[] a, int sum){
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int element : a){
			map.put(sum - element, element);
			if(map.containsKey(element)) return true;
		}
		return false;
	}
	
	
	/**
	 * Problem 1.10 in AFI: Given two text documents L and M, determine if
	 * it is possible to write L using letters from M (without replacement)
	 * @param l string representing document L
	 * @param m string representing document M
	 * @return true if L can be written using M
	 */
	public static boolean canBeWritten(String l, String m){
		HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
		
		for(char c : m.toCharArray()){
			int key = (int) c;
			Integer count = countMap.get(key);
			if(count == null) countMap.put(key, 1);
			else countMap.put(key, count + 1);
		}
		
		for(char c : l.toCharArray()){
			int key = (int) c;
			Integer count = countMap.get(key);
			if(count == null || count == 0) return false;
			else countMap.put(key, count - 1);
		}
		
		return true;
	}
	
	
	
	/**
	 * User class for Problem 1.11 in AFI
	 */
	public class User{
		private Integer key;
		private Set<String> attributes;
		
		public User(Integer key, Set<String> attributes) {
			super();
			this.key = key;
			this.attributes = attributes;
		}
		
		public Integer getKey() {
			return key;
		}
		
		public void setKey(Integer key) {
			this.key = key;
		}
		
		public Set<String> getAttributes() {
			return attributes;
		}
		
		public void setAttributes(Set<String> attributes) {
			this.attributes = attributes;
		}
		
	}
	
	
	/**
	 * Problem 1.11a in AFI: Given a list of Users having a key and a set of String
	 * attributes, find pairs of users that have exactly the same attributes
	 * @param userList list of users
	 * @return a Map containing pairs of users with matching attributes
	 */
	public static Map<Integer, Integer> exactMatchUsers(List<User> userList){
		HashMap<Set<String>, Integer> attrMap = new HashMap<Set<String>, Integer>();
		HashMap<Integer, Integer> userPairs = new HashMap<Integer, Integer>();
		
		for(User userA : userList){
			Set<String> userAAttr = userA.getAttributes();
			Integer userBKey = attrMap.get(userAAttr);
			
			if(userBKey == null) attrMap.put(userAAttr, userA.getKey());
			else{
				userPairs.put(userA.getKey(), userBKey);
				attrMap.remove(userAAttr);
			}
		}
		
		return userPairs;
	}
	
	
	/**
	 * Problem 1.11b in AFI: Given a list of Users having a key and a set of String
	 * attributes, find pairs of users that have at least one attribute in common
	 * @param userList list of users
	 * @return a Map containing pairs of users with a common attribute
	 */
	public static Map<Integer, Integer> approxMatchUsers(List<User> userList){
		return null; //TODO implement
	}
	
	
	/**
	 * Problem 1.13 in AFI (rephrased): find the highest climb given a sequence
	 * of heights (not necessarily consecutive)
	 * @param heights list of heights climbed in order
	 * @return highest climb of the sequence
	 */
	public static int findHighestClimb(int[] heights){
		int lowestPoint = Integer.MAX_VALUE;
		int highestClimb = 0;
		
		for(int h : heights){
			if(h - lowestPoint > highestClimb) highestClimb = h - lowestPoint;
			if(h < lowestPoint) lowestPoint = h;
		}
		
		return highestClimb;
	}
	
	
	/**
	 * Problem 1.14 in AFI: given an arbitrarily large stream of words and knowing
	 * a priori that there exists a majority word that occurs more than half the
	 * time, find the majority word
	 * @param stream a list of words
	 * @return majority word
	 */
	public static String findMajority(List<String> stream){
		if(stream.size() == 0) return "";
		String majorityWord = stream.get(0);
		int count = 0;
		
		for(String word : stream){
			if( !word.equals(majorityWord) ) count--;
			else count++;
			
			if(count == 0){
				majorityWord = word;
				count = 1;
			}
		}
		
		return majorityWord;
	}
	
	
	/**
	 * Problem 1.15 in AFI: given an stream of N words, and integer K, find items that
	 * occur more than N/K times
	 * @param stream a list of words
	 * @param k parameter k
	 * @return list of frequent word that occur more than N/K times
	 */
	public static List<String> findFrequent(List<String> stream, int k){
		
		HashMap<String, Integer> counter = new HashMap<String, Integer>(k);
		
		for(String word : stream){
			if(counter.containsKey(word)) counter.put(word, counter.get(word) + 1);
			else{
				if(counter.size() == k){
					for(String key : counter.keySet()){
						int count = counter.get(key);
						if(count == 1) counter.remove(key);
						else counter.put(key, count - 1);
					}
				}
				counter.put(word, 1);
			}
		}
		
		// Set all counters of the current words to 1 for the 2nd pass
		for(String key : counter.keySet()){
			counter.put(key, 1);
		}
		
		// Do a 2nd pass and calculate actual counts
		List<String> freqWords = new LinkedList<String>();
		for(String word : stream){
			if(counter.containsKey(word)){
				int newCount = counter.get(word) + 1;
				if(newCount > Math.ceil((double)stream.size()/k)){
					freqWords.add(word);
					counter.remove(word);
				}
				else counter.put(word, newCount);
				
			}
		}
		
		return freqWords;
	}
}
